// msort.c
// LMNO LALR(1) parser generator
//
// Copyright ©2010 Brigham Toskin
// (Based on LEMON v1 parser generator, public domain)
//////////////////////////////////////////////////////


#include "global.h"


/*
 ** A generic merge-sort program.
 **
 ** USAGE:
 ** Let "ptr" be a pointer to some structure which is at the head of
 ** a null-terminated list.  Then to sort the list call:
 **
 **	 ptr = msort(ptr,&(ptr->next),cmpfnc);
 **
 ** In the above, "cmpfnc" is a pointer to a function which compares
 ** two instances of the structure and returns an integer, as in
 ** strcmp.  The second argument is a pointer to the pointer to the
 ** second element of the linked list.  This address is used to compute
 ** the offset to the "next" field within the structure.  The offset to
 ** the "next" field must be constant for all structures in the list.
 **
 ** The function returns a new pointer which is the head of the list
 ** after sorting.
 **
 ** ALGORITHM:
 ** Merge-sort.
 */

/*
 ** Return a pointer to the next structure in the linked list.
 */
#define NEXT(A) (*(char**)(((unsigned long)A)+offset))

/*
 ** Inputs:
 **   a:	   A sorted, null-terminated linked list.  (May be null).
 **   b:	   A sorted, null-terminated linked list.  (May be null).
 **   cmp:	 A pointer to the comparison function.
 **   offset:  Offset in the structure to the "next" field.
 **
 ** Return Value:
 **   A pointer to the head of a sorted list containing the elements
 **   of both a and b.
 **
 ** Side effects:
 **   The "next" pointers for elements in the lists a and b are
 **   changed.
 */
static char *merge(char *a, char *b, int (*cmp)(), int offset)
{
	char *ptr, *head;
	
	if( a==0 )
	{
		head = b;
	}
	else if( b==0 )
	{
		head = a;
	}
	else
	{
		if( (*cmp)(a,b)<0 )
		{
			ptr = a;
			a = NEXT(a);
		}
		else
		{
			ptr = b;
			b = NEXT(b);
		}
		head = ptr;
		while( a && b )
		{
			if( (*cmp)(a,b)<0 )
			{
				NEXT(ptr) = a;
				ptr = a;
				a = NEXT(a);
			}
			else
			{
				NEXT(ptr) = b;
				ptr = b;
				b = NEXT(b);
			}
		}
		if( a )
			NEXT(ptr) = a;
		else
			NEXT(ptr) = b;
	}
	return head;
}

/*
 ** Inputs:
 **   list:	  Pointer to a singly-linked list of structures.
 **   next:	  Pointer to pointer to the second element of the list.
 **   cmp:	   A comparison function.
 **
 ** Return Value:
 **   A pointer to the head of a sorted list containing the elements
 **   orginally in list.
 **
 ** Side effects:
 **   The "next" pointers for elements in list are changed.
 */
#define LISTSIZE 30
char *msort(char *list, char **next, int (*cmp)())
{
	unsigned long offset;
	char *ep;
	char *set[LISTSIZE];
	int i;
	offset = (unsigned long)next - (unsigned long)list;
	for(i=0; i<LISTSIZE; i++)
		set[i] = 0;
	while( list )
	{
		ep = list;
		list = NEXT(list);
		NEXT(ep) = 0;
		for(i=0; i<LISTSIZE-1 && set[i]!=0; i++)
		{
			ep = merge(ep,set[i],cmp,offset);
			set[i] = 0;
		}
		set[i] = ep;
	}
	ep = 0;
	for(i=0; i<LISTSIZE; i++)
		if( set[i] )
			ep = merge(ep,set[i],cmp,offset);
	return ep;
}
